package com.algo.QFS;

/**
 * @Author: guoxing
 * @Email: gx_study2022@163.com
 * @Description: https://blog.csdn.net/weixin_37980595/article/details/125443270?spm=1001.2014.3001.5502
 * @Date: 2024/6/25 9:12
 * @ClassName: HungarianAlgorithm
 **/
import java.util.Arrays;

public class HungarianAlgorithm{
    double[][] a;
    double m[][];
    public HungarianAlgorithm(double[][] a){
        this.a=new double[a.length][a[0].length];
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a[i].length;j++){
                this.a[i][j]=a[i][j];
            }
        }
    }
    public static void main(String[] args) {
        double[][] a = { { 12, 7, 9, 7, 9 }, { 8, 9, 6, 6, 6 }, { 7, 17, 12, 14, 9 }, { 15, 14, 6, 6, 10 },
                { 4, 10, 7, 10, 9 } };
        HungarianAlgorithm lp=new HungarianAlgorithm(a);
        lp.hungarianMethod();


    }
    public void hungarianMethod(){
        int L = a.length;
        int S = a[1].length;
        if (L <= S) {
            double[][] b = new double[S - L][S];
            for (int i = 0; i < S - L; i++) {
                for (int j = 0; j < S; j++) {
                    b[i][j] = 0;
                }
            }

            m = Arrays.copyOf(a, a.length + b.length);
            System.arraycopy(b, 0, m, a.length, b.length);

            int N = m.length;
            double[][] c = new double[N][N];
            c = copy(m, c);

            guiyue(m);
            tryAppoint(m);


            double finalAnswer = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (m[i][j] == -1) {
                        finalAnswer += c[i][j];
                    }
                }
            }
        }
    }
    public static void guiyue(double[][] m) {
        int N = m.length;

        for (int i = 0; i < N; i++) {
            double min = Double.MAX_VALUE;
            for (int j = 0; j < N; j++) {
                if (m[i][j] < min) {
                    min = m[i][j];
                }
            }

            for (int j = 0; j < N; j++) {
                m[i][j] -= min;

            }
        }

        for (int j = 0; j < N; j++) {
            double min = Double.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                if (m[i][j] < min) {
                    min = m[i][j];
                }
            }
            for (int i = 0; i < N; i++) {
                m[i][j] -= min;
            }
        }

    }

    public static void tryAppoint(double[][] m) {
        int N = m.length;

        int zeroNumber = 0;
        int zeroNumber1 = -1;

        while (zeroNumber1 != zeroNumber) {
            zeroNumber1 = zeroNumber;
            rowsAppoint(m);
            colsAppoint(m);
            zeroNumber = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (m[i][j] == 0) {
                        zeroNumber += 1;
                    }
                }
            }

        }
        do {
            rowsAppoint2(m);
        } while (rowsAppoint2(m));


        if (judge(m)) {
            printResult(m);
        } else {
            drawZeroLine(m);
        }
    }

    public static void drawZeroLine(double[][] m) {
        int N = m.length;

        boolean[] rowIsChecked = new boolean[N];
        boolean[] colIsChecked = new boolean[N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (m[i][j] == -1) {
                    rowIsChecked[i] = false;
                    break;
                } else {
                    rowIsChecked[i] = true;
                }
            }
        }

        for (int j = 0; j < N; j++) {
            colIsChecked[j] = false;
        }

        int trueCount = 0;
        int trueCount1 = -1;

        while (trueCount1 != trueCount) {
            trueCount1 = trueCount;

            for (int i = 0; i < N; i++) {
                if (rowIsChecked[i]) {
                    for (int j = 0; j < N; j++) {
                        if (m[i][j] == -2) {
                            colIsChecked[j] = true;
                        }
                    }
                }
            }

            for (int j = 0; j < N; j++) {
                if (colIsChecked[j]) {
                    for (int i = 0; i < N; i++) {
                        if (m[i][j] == -1) {
                            rowIsChecked[i] = true;
                        }
                    }
                }
            }

            trueCount = 0;
            for (int i = 0; i < N; i++) {
                if (rowIsChecked[i] == true) {
                    trueCount += 1;
                }
            }
            for (int j = 0; j < N; j++) {
                if (colIsChecked[j] == true) {
                    trueCount += 1;
                }
            }
        }

        int lineCount = 0;
        for (int i = 0; i < N; i++) {
            if (rowIsChecked[i] == false) {
                lineCount += 1;
            }
        }
        for (int j = 0; j < N; j++) {
            if (colIsChecked[j] == true) {
                lineCount += 1;
            }
        }
        if (lineCount < N) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (m[i][j] < 0) {
                        m[i][j] = 0;
                    }
                }
            }
            double minValue = Double.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (rowIsChecked[i] == true && colIsChecked[j] == false) {
                        if (m[i][j] < minValue) {
                            minValue = m[i][j];
                        }
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (rowIsChecked[i] == true) {
                        m[i][j] -= minValue;
                    }
                    if (colIsChecked[j] == true) {
                        m[i][j] += minValue;
                    }
                }
            }
            tryAppoint(m);
        } else if (lineCount == N) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (m[i][j] < 0) {
                        m[i][j] = 0;
                    }
                }
            }

            tryAppoint(m);
        }
    }

    public static void rowsAppoint(double[][] m) {
        int N = m.length;
        for (int i = 0; i < N; i++) {
            int rowCount = 0;
            int colIndex = Integer.MIN_VALUE;
            for (int j = 0; j < N; j++) {
                if (m[i][j] == 0) {
                    rowCount += 1;
                    colIndex = j;
                }
            }

            if (rowCount == 1) {
                m[i][colIndex] = -1;
                for (int i1 = 0; i1 < N; i1++) {

                    if (i1 == i) {
                        continue;
                    } else if (m[i1][colIndex] == 0) {
                        m[i1][colIndex] = -2;
                    }
                }

            }

        }
    }

    public static boolean rowsAppoint2(double[][] m) {
        boolean zeroExist = false;
        int N = m.length;
        int rowZeroNumber = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            int rowZeroCount = 0;
            for (int j = 0; j < N; j++) {
                if (m[i][j] == 0) {
                    rowZeroCount += 1;
                    zeroExist = true;
                }
            }
            if (rowZeroCount < rowZeroNumber && rowZeroCount != 0) {
                rowZeroNumber = rowZeroCount;

            }
        }

        for (int i = 0; i < N; i++) {
            int rowCount = 0;
            int colIndex = Integer.MAX_VALUE;
            for (int j = 0; j < N; j++) {
                if (m[i][j] == 0) {
                    rowCount += 1;
                    colIndex = j;
                    zeroExist = true;
                }
            }
            if (rowCount == rowZeroNumber) {
                if (Math.random() > 0.95) {
                    for (int i1 = 0; i1 < N; i1++) {
                        if (m[i1][colIndex] == 0) {
                            m[i1][colIndex] = -2;
                        }
                    }
                    for (int j1 = 0; j1 < N; j1++) {
                        if (m[i][j1] == 0) {
                            m[i][j1] = -2;
                        }
                    }
                    m[i][colIndex] = -1;

                    break;
                }
            }
        }
        return zeroExist;
    }

    public static void colsAppoint(double[][] m) {
        int N = m.length;
        for (int j = 0; j < N; j++) {
            int colCount = 0;
            int rowIndex = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                if (m[i][j] == 0) {
                    colCount += 1;
                    rowIndex = i;
                }
            }

            if (colCount == 1) {
                m[rowIndex][j] = -1;
                for (int j1 = 0; j1 < N; j1++) {

                    if (j1 == j) {
                        continue;
                    } else if (m[rowIndex][j1] == 0) {
                        m[rowIndex][j1] = -2;
                    }
                }

            }
        }

    }

    public static boolean judge(double[][] m) {
        int count = 0;
        int N = m.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (m[i][j] == -1) {
                    count += 1;
                }
            }
        }
        return count == N;
    }

    public static double[][] copy(double[][] m, double[][] a) {
        int N = m.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                a[i][j] = m[i][j];
            }
        }
        return (a);
    }

    public static void printM(double[][] m) {
        int N = m.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(m[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void printResult(double[][] m) {
        int N = m.length;
        double finalAnswer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (m[i][j] == -1) {
                    System.out.print((i + 1) + "--" + (j + 1) + "  ");
                }
            }
        }
    }
}
